package rsa.lib;

import java.math.BigInteger;

public class ExtendedEulid {
	
	//  return array [d, a, b] such that d = gcd(p, q), ap + bq = d
	static BigInteger[] gcd(BigInteger p, BigInteger q){
		if(q.compareTo(BigInteger.ZERO) == 0)
			return new BigInteger[]{p, new BigInteger("1"), new BigInteger("0")};
		BigInteger[] vals = gcd(q, p.mod(q));
		BigInteger d = vals[0];
		BigInteger a = vals[2];
		BigInteger b = vals[1].subtract((p.divide(q)).multiply(vals[2]));
		return new BigInteger[] {d, a, b};
	}
	
	static public BigInteger inverseModule(BigInteger a, BigInteger r){
		BigInteger[] result = gcd(a, r);
		if(result[0].compareTo(BigInteger.ONE)==0){
			if(result[1].compareTo(BigInteger.ZERO) < 0)
				return r.add(result[1]);
			else
				return result[1];
		}
		else
			return BigInteger.ZERO;
	}
}
